package foundation.图论;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author hang an
 * @since 2025/7/14
 */
public class 拓扑排序_课程表 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int[]in = new int[numCourses];
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] cur : prerequisites) {
            int u = cur[0];
            int v = cur[1];
            in[u]++;
            list.get(v).add(u);
        }
        int cnt = 0;
        Queue<Integer> q = new LinkedList<>();
        // 先将入度为0的节点入队
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                q.add(i);
            }
        }
        // 每一次都将队头节点的入度减1，如果入度减为0，则将节点入队
        while (!q.isEmpty()) {
            int cur = q.poll();
            res[cnt] = cur;
            cnt++;
            for (int next : list.get(cur)) {
                in[next]--;
                if (in[next] == 0) {
                    q.add(next);
                }
            }
        }
        return cnt == numCourses ? res : new int[]{};
    }


}
